package com.lisp.algorithm.test.sort;

import java.util.HashMap;

public class MultipleK {

	public static void main(String[] args) {
		int a[] = {1, 8, 10, 2, 5, 4};
		int[] multipleK = multipleK(a, 19);
		ArrayUtils.print(multipleK);
	}
	
	private static int[] multipleK(int a[], int k) {
		for(int i=1, len=a.length; i<len; i++) {
			a[i] = a[i] + a[i-1];
		}
		
		HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		for(int i=0, len=a.length; i<len; i++) {
			int remainder = a[i] % k;
			if(remainder == 0 && i>0) {
				return new int[] {0, i};
			}
			
			Integer index = hashMap.get(remainder);
			if(index != null && i-index>1) {
				return new int[] {index+1, i};
			} else {				
				hashMap.put(remainder, i);
			}
		}
		
		return null;
	}
}
